P4358 [CQOI2016]密钥破解

这道题没有想象中的那么难,只不过板子P4718 【模板】Pollard-Rho算法是黑的(为什么这道题是紫的

既然题目保证nn为两质数p,qp,q乘积。我们可以用
Pollard RhoPollard~Rho求出p,qp,q

然后跟着题目一步步模拟,计算r=(p1)(q1)r=(p-1)*(q-1)

然后根据ed1(mod r)ed≡1(mod~r)计算dd(我用的扩欧)。

最后,用快速幂求出ncd(mod N)n≡c^d(mod~N)

因为数据范围很大,我用的是__int128,注意它不能用标准输入输出,要手写读优输优。

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
#define int __int128

void Read( int &x ) {
	x = 0;int f = 1;
	char s = getchar( );
	while( s < '0' || s > '9' ) {
		if( s == '-' ) f = -1;
		s = getchar( );
	}
	while( '0' <= s && s <= '9' ) {
		x = x * 10 + s - '0';
		s = getchar( );
	}
	x *= f;
}
void Write( int x ) {
	if( x < 0 ) {
		x = -x;
		putchar('-');
	}
	if( x >= 10 )
		Write( x / 10 );
	putchar( x % 10 + '0' );
}

int Exgcd( int a , int b , int &x , int &y ) {
	if( !b ) {
		x = 1 , y = 0;
		return a;
	}
	else {
		int r = Exgcd( b , a % b , y , x );
		y -= x * ( a / b );
		return r;
	}
}
int Gcd( int x , int y ) {
	return y == 0 ? x : Gcd( y , x % y );
}
int Abs( int x ) {
	return x >= 0 ? x : -x;
}
int f( int x , int a , int Mod ) {
	return ( x * x + a ) % Mod;
}
int Quick_pow( int x , int po , int Mod ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 )
			Ans = Ans * x % Mod;
		x = x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x , int Mod ) {
	int u , v;
	Exgcd( x , Mod , u , v );
	return ( u % Mod + Mod ) % Mod;
}

int Pollard_rho( int n ) {
	int r = rand( ) % ( n - 1 ) + 1;
	int a = f( 0 , r , n ) , b = f( f( 0 , r , n ) , r , n ); 
	while( b != a ) {
		int p = Gcd( Abs( b - a ) , n );
		if( p > 1 ) return p;
		a = f( a , r , n ) , b = f( f( b , r , n ) , r , n );
	}
	return n;
}

int N , e , c , p , q , r , d , n; 
signed main( ) {
	srand( 20060204 );
	
	Read( e ) , Read( N ) , Read( c ); 
	p = Pollard_rho( N ) , q = N / p;
	r = ( p - 1 ) * ( q - 1 );
	d = Inv( e , r );
	n = Quick_pow( c , d , N );
	/*Write( d ) , putchar('\n');
	Write( n ) , putchar('\n');
	Write( p ) , putchar('\n');
	Write( q ) , putchar('\n');
	Write( r ) , putchar('\n'); */
	Write( d ) , putchar(' ') , Write( n ); 
	return 0;
}